1. Field of the Invention
This invention relates to a data processing system and a scheduling method which, for use in a data processing system composed of a central processing unit and an auxiliary processing unit provided in, and running in parallel with, the central processing unit, allow the central processing unit to schedule processes to be executed in an auxiliary processing unit so that the auxiliary processing unit may perform special processing efficiently.
2. Description of the Related Art
Recently, a need has arisen to process multimedia data, including voice data, image data, and communication data, through software. Because multimedia processing involves a large amount of data which must be processed at a high speed and in parallel, the central processing unit contains, in many cases, an auxiliary processing unit specifically designed to perform multimedia processing in parallel with the central processing unit. In such a configuration, the central processing unit is responsible for controlling the system and scheduling jobs to enable the auxiliary processing unit to efficiently perform multimedia processing within a limited time, while the auxiliary processing unit performs only specified multimedia processing according to schedules arranged by the central processing unit.
Two or more multimedia processes, each of which requires a long time, must usually be processed in parallel. However, depending upon the status of the auxiliary processing unit, performing such multimedia processes in the above-described configuration sometimes results in parallel processing not being performed smoothly and, in the worst case, intended processing not being completed within the time limit. A typical example of this problem is that a time-critical, high-priority multimedia process must be executed while a low-priority multimedia process is being executed. In this case, the central processing unit of a conventional system has used one of the following methods to schedule the auxiliary processing unit:
(1) Interrupts the current processing of the auxiliary processing unit and saves the status of the processing. For example, the central processing unit saves the data stored in all registers. Then, the auxiliary processing unit executes the higher-priority process, restores the saved status data when the higher-priority process ends, and restarts the interrupted process.
(2) Stops the current processing executed by the auxiliary processing unit, discards all status data, and executes the higher-priority process. When the processing of the higher-priority process ends, the central processing unit restarts the discarded process from the beginning or, instead of restarting the discarded process from the beginning, cancels the process and executes some alternate processing.
(3) Waits for the auxiliary processing unit to end the current processing and then executes the next process.
The scheduling method described in (1) is commonly used in usual multiprocessing. However, because standard multimedia processes usually use many registers, this method sometimes takes long in saving and restoring them. The scheduling method described in (2) is sometimes used in multimedia processing. Because discarding status data requires much less time than saving it, this method has an advantage over the scheduling method described in (1)in that processes are switched quickly. In addition, alternate processing, if done optimally, reduces the overall system load. The scheduling method described in (3) is useful when, instead of saving or discarding the current process status data and then switching processes, completing the current process results in the high-priority process being executed more quickly. Depending upon the status of the process in execution, this method is more efficient.
Using these scheduling methods to flexibly schedule the auxiliary processing unit which performs multimedia processing increases overall system efficiency. However, the conventional auxiliary processing unit has no means for reporting the progress status of the current process to the central processing unit. Thus, when the auxiliary processing unit need to process a high-priority multimedia process during execution of a low-priority multimedia process, the central processing unit has no way to determine which of the above-described scheduling methods will be best to complete the high-priority multimedia process within the time limit without increasing the overall system load. The central processing unit of the conventional system has selected either scheduling method (1) or (2) to schedule any multimedia process it receives.
Assume that the scheduling method (1) is used. In the example shown in FIG. 1A, process A currently in execution is interrupted, the status data is saved, and process B which follows process A is executed and is completed within the time limit. In the example shown in FIG. 1B, there is no time to save the status of process A and therefore process B cannot be completed within the time limit. In the example shown in FIG. 1C, process B is completed within the time limit. However, process B may also be completed even if it is executed after process A. Moreover, the status must be restored after termination of process B to restart process A. Therefore, the scheduling method is inefficient in this case because scheduling involves meaningless process switching with an increase in the amount of overall system processing.
Assume that the scheduling method (2) is used. In the example shown in FIG. 2A, process A currently in execution is interrupted, the status data is discarded, and process B that follows is executed and is completed within the time limit of process B. However, because process A must be executed from the beginning in this case after process B is ended, the total amount of processing becomes very large. In the example shown in FIG. 2B, there is no time to save the status of process A. So, process A must be restarted from the beginning in order to end higher-priority process B within the time limit. On the other hand, the example shown in FIG. 2C is inefficient because it is similar to the one shown in FIG. 1C. The need to execute process A from the beginning involves meaningless process switching with an increase in the amount of overall system processing.
As described above, the central processing unit in the conventional data processing system, in which the auxiliary processing unit is provided to execute multimedia processing and so forth according to the schedule arranged by the central processing unit, cannot keep track of the progress status of a process the auxiliary processing unit is currently executing. Therefore, the central processing unit selects one of a plurality of scheduling methods and, according to the selected scheduling method, schedules the processes the auxiliary processing unit is going to execute. This prevents optimized scheduling and so prevents the auxiliary processing unit from executing processing efficiently.
In view of the foregoing, it is an object of this invention to provide a data processing system and a scheduling method which optimally schedule special processes to be executed by the auxiliary processing unit according to a schedule arranged by the central processing unit in order to allow the auxiliary processing unit to execute special processes efficiently.
To achieve the above object, there is provided a data processing system comprising a central processing unit; an auxiliary processing unit which runs in parallel with the central processing unit and which executes a special process according to a schedule made by the central processing unit, wherein the auxiliary processing unit comprises progress status indicating means for indicating a progress status of the special process being executed therein; and operation status indicating means for indicating an operation status thereof, and wherein the central processing unit comprises a database which stores a predetermined execution processing time of each special process; and scheduling means, responsive to a new process request received when the operation status indicating means indicates that a preceding special process is being executed in the auxiliary processing unit and the new special process is higher in priority than the preceding special process, for selecting any one of ending the preceding special process, interrupting the preceding special process and saving a processing status, and interrupting the preceding special process and discarding the processing status, based on a limit time from the moment the new process request is received to the moment the new special process must be ended, the processing time of the new special process, the processing time being stored in the database, a time required for the preceding special process to end, the time being obtained by referencing the progress status indicating means of the auxiliary processing unit, and a time required to interrupt the preceding special process being executed in the auxiliary processing unit and to save or discard the processing status, and then for scheduling a time at which the new special process is to start.
To achieve the above object, there is provided a data processing system comprising a central processing unit; and an auxiliary processing unit which runs in parallel with the central processing unit and which executes a special process according to a schedule made by the central processing unit, wherein the auxiliary processing unit comprises progress status indicating means for indicating a progress status of the special process being executed therein; and operation status indicating means for indicating an operation status thereof, and wherein the central processing unit comprises a database which stores a predetermined execution processing time of each special process; and scheduling means, responsive to a request received when the operation status indicating means indicates that a preceding special process is being executed in the auxiliary processing unit and the new special process is higher in priority than the preceding special process, for calculating a limit time, Ta, from the moment the new process request is received to the moment the new special process must be ended, retrieving the processing time, Tb, of the new special process from the database, calculating a latest start time, Tc, before which the new special process must be started to complete within the limit time by subtracting the processing time Tb from the limit time Ta, and calculating a time, Td, when the preceding special process is to end by referencing the progress status indicating means of the auxiliary processing unit, wherein the new special process is scheduled to start after the preceding special process is ended if Tcxe2x89xa7Td, wherein the preceding special process is interrupted, the processing status is saved, and then the new special process is scheduled to start if Tc less than Td and Tcxe2x89xa7Te, and wherein the preceding special process is interrupted, the processing status is discarded, and then new special process is scheduled to start if Tc less than Td, Tc less than Te, and Tcxe2x89xa7Tf, Te being a time at which the processing status of the interrupted preceding special process in the auxiliary processing unit is saved, Tf being a time at which the processing status of the interrupted preceding special process in the auxiliary processing unit is discarded.
In a preferred embodiment of this invention, the progress status indicating means is initialized to 0 when the special process is started and comprises a counter which is incremented by the number of instructions executed as the special process progresses.
In a preferred embodiment of this invention, the progress status indicating means is set to the time required to execute the special process when the auxiliary processing unit starts the special process, and comprises a counter which is decremented by the number of instructions executed as the special process progresses.
In a preferred embodiment of this invention, the value of the counter is reset according to the content of processing at any time during the special processing.
To achieve the above object, there is provided a scheduling method for allowing a central processing unit to schedule special processes to be executed in an auxiliary processing unit, in response to a new special process request received by the central processing unit when a preceding special process is being executed in the auxiliary processing unit and the new special process is higher in priority than the preceding special process, comprising the steps of selecting any one of ending the preceding special process, interrupting the preceding special process and saving a processing status, and interrupting the preceding special process and discarding the processing status, based on a limit time from the moment the new process request is received to the moment the new special process must be ended, a processing time of the new special process, a time from the moment the request is received to the moment the preceding special process is to end; and a time required to interrupt the preceding special process being executed in the auxiliary processing unit and to save or discard the processing status; and scheduling a time at which the new special process is to start.
To achieve the above object, there is provided a scheduling method for allowing a central processing unit to schedule special processes to be executed in an auxiliary processing unit, in response to a new special process request received by the central processing unit when a preceding special process is being executed in the auxiliary processing unit and the new special process is higher in priority than the preceding special process, comprising the steps of calculating a limit time, Ta, from the moment the new process request is received to the moment the new special process must be ended; retrieving a processing time, Tb, of the new special process and calculating a latest start time, Tc, before which the new special process must be started to complete within the limit time by subtracting the processing time Tb from the limit time Ta; calculating a time, Td, when the preceding special process is to end; starting the new special process after the preceding special process is ended if Tcxe2x89xa7Td; interrupting the preceding special process, saving the processing status, and then starting the new special process if Tc less than Td and Tcxe2x89xa7Te, Te being a time at which the processing status of the interrupted preceding special process in the auxiliary processing unit is saved; and interrupting the preceding special process, discarding the processing status, and then starting the new special process if Tc less than Td, Tc less than Te, and Tcxe2x89xa7Tf, Tf being a time at which the processing status of the interrupted preceding special process in the auxiliary processing unit is discarded.
The nature, principle and utility of the invention will become more apparent from the following detailed description when read in conjunction with the accompanying drawings.